import java.util.*;

public class project {
    public int minFlips(int a, int b, int c) {
        int ret=0;
        while (c!=0||a!=0||b!=0){
            int aa=a&1;
            int bb=b&1;
            int cc=c&1;
            a>>=1;
            b>>=1;
            c>>=1;
            if((aa|bb)==cc){
                continue;
            }
            if(cc==1){
                ret++;
            }else{
                if(aa==1){
                    ret++;
                }
                if(bb==1){
                    ret++;
                }
            }

        }
        return ret;
    }

















    public int getMinimumTime(int[] time, int[][] fruits, int limit) {
        int ret=0;
        for(int[] fruit:fruits){
            int count=fruit[1]%limit==0?fruit[1]/limit:fruit[1]/limit+1;
            ret+=count*time[fruit[0]];
        }
        return ret;
    }















    public boolean validPath(int n, int[][] edges, int source, int destination) {
        if(n==1){
            return true;
        }
        List<Integer>[] lists=new ArrayList[n];
        for(int i=0;i<n;i++){
            lists[i]=new ArrayList<>();
        }
        for(int[] edge:edges){
            lists[edge[0]].add(edge[1]);
            lists[edge[1]].add(edge[0]);
        }
        Queue<Integer> queue=new ArrayDeque<>();
        boolean[] flag=new boolean[n];
        queue.add(source);
        while (!queue.isEmpty()){
            int prev=queue.poll();
            for(int cur:lists[prev]){
                if(cur==destination){
                    return true;
                }
                if(!flag[cur]){
                    flag[cur]=true;
                    queue.add(cur);
                }
            }
        }
        return false;
    }



















    public List<Integer> intersection(int[][] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int[] num:nums){
            for(int value:num){
                map.put(value,map.getOrDefault(value,0)+1);
            }
        }
        List<Integer> list=new LinkedList<>();
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()==nums.length){
                list.add(entry.getKey());
            }
        }
        Collections.sort(list);
        return list;
    }

















    int[][] dir=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int row;
    int col;
    int[][] nums;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.row=heights.length;
        this.col=heights[0].length;
        this.nums=heights;
        boolean[][] p=new boolean[row][col];
        boolean[][] a=new boolean[row][col];
        List<List<Integer>>ret=new LinkedList<>();
        for(int i=0;i<row;i++){
            dfs(i,0,p);
        }
        for(int i=1;i<col;i++){
            dfs(0,i,p);
        }
        for(int i=0;i<row;i++){
            dfs(i,col-1,a);
        }
        for(int i=0;i<col-1;i++){
            dfs(row-1,i,a);
        }
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(p[i][j]&&a[i][j]){
                    List<Integer> list=new LinkedList<>();
                    list.add(i);
                    list.add(j);
                    ret.add(list);
                }
            }
        }
        return ret;
    }
    public void dfs(int x,int y,boolean[][] flag){
        if(flag[x][y]){
            return;
        }
        flag[x][y]=true;
        for(int[] d:dir){
            int newX=x+d[0];
            int newY=y+d[1];
            if(newX>=0&&newY>=0&&newX<row&&newY<col&&nums[newX][newY]>=nums[x][y]){
                dfs(newX,newY,flag);
            }
        }
    }
}
